package leetcode;

import java.util.Arrays;

public class LongestPalindromicSubstring {
	
    private int low, maxLength;
    
    //运行时间15ms
    public String longestPalindrome(String s) {
        int length = s.length();
        low = 0;
        maxLength = 0;
        if(length < 2){
            return s;
        }
        for (int i = 0; i < length - 1; i++) {
     	        extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
     	        extendPalindrome(s, i, i + 1); //assume even length.
        }
        return s.substring(low, low + maxLength);
	}
	
	private void extendPalindrome(String s, int j, int k) {
	    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		    j--;
		    k++;
	    }
	    if (maxLength < (k - 1) - (j + 1) + 1) {
		    low = j + 1;
		    maxLength = k - j - 1;
	    }
	}
	
	
	public static void main(String[] args) {
		LongestPalindromicSubstring object = new LongestPalindromicSubstring();
//		System.out.println(object.longestPalindrome2("zkabababajki"));
//		System.out.println(object.longestPalindrome2("zmaaaamno"));
		
		System.out.println(object.longest("abzcdef", "bzdefghi"));
	}
	
	
	//然而这个的效率也不高，运行时间28ms
	public String longestPalindrome2(String s) {
        if(s == null || s.length() <= 0){
        	return s;
        }
        return longestPalindromeManacher(s);
	}
	
	public String longestPalindromeManacher(String s) {
		String T = preProcess(s);
		int len = T.length(); // 经过变化后，len总是为奇数长
		
		// P数组存放在以index为中心的回文半径长度
		int[] radius = new int[len];
		int C = 0, R = 0; // C为最长回文子串的中心位置，R为当前最长回文子串的右边界位置
		// 第0个字符和最后一个字符是无效字符，仅为了避免边界检查
		for (int i = 1; i < len - 1; i++) {
			// 计算i以C为中心的对应回文左边匹配位置
			//C 等于上一轮的j
			int iMirror = 2 * C - i;

			// R > i 表示i...R是回文串的右半部分
			//初始iMirror为-1，但是此时R < i
			//R为f(j) / 2 + C
			//那这个为什么不是f(j) + 2 * C - 2 * i呢，因为这儿存储的是半径，所以长度为 原有的 / 2
			radius[i] = (R > i) ? Math.min(R - i, radius[iMirror]) : 0;

			// 贪心拓展以i为回文中心的回文子串
			while (T.charAt(i + radius[i] + 1) == T.charAt(i - radius[i] - 1)) {
				radius[i]++;
			}

			// 如果以i为中心的回文扩展超过了R，则我们找到一个新的更长回文子串
			// 因此 更新 最长回文子串的中心和右边界
			if (radius[i] > R - i) {
				C = i;
				R = i + radius[i];
			}
		}

		// 现在P[i]数组里存放了以i为中心的回文子串长度，用打擂台方式找到最长者
		int maxLen = 0;
		int j = 0;
		for (int i = 1; i < len - 1; i++) {
			System.out.println(i + " " + radius[i]);
			if (radius[i] > maxLen) {
				maxLen = radius[i];
				j = i / 2 - 1;
			}
		}
		System.out.println(j + " " + maxLen);
		if( (maxLen & 1) == 0){
			return s.substring(j - maxLen / 2 + 1, j + maxLen / 2 + 1);
		}else{
			return s.substring(j - maxLen / 2, j + maxLen / 2 + 1);
		}
	}
	
	private String preProcess(String s) {
		int len = s.length();
		if (len == 0) {
			return "^$";
		}
		StringBuilder ret = new StringBuilder(2 * len + 3);
		ret.append("^");
		for (int i = 0; i < len; i++) {
			ret.append('#').append(s.charAt(i));
		}
		ret.append("#$");
		return ret.toString();
	}
	
	
    //刚开始的思路都错了，下面的方法可以求最长回文子序列，但不是最长回文子串
	//比如 "abcdasdfghjkldcba"
    public String longestPalindrome3(String s) {
        return null;
    }
	
    
    
    //求最长回文子序列，也就是求和转置后的String的最长公共子序列
    public String longestPalindromeSubsequece(String s) {
         if(s == null || s.length() <= 0){
        	 return "";
         }
         String reverse = new StringBuilder(s).reverse().toString();
         return getLongest(s, reverse);
	}
	
	//result[i][j] 表示表示以i结尾的子串和以j结尾的子串最大的公共长度
	public  String getLongest(String S, String T){
		if (S == null || T == null) {
			return "";
		}
		if(S.length() <= 0  || T.length() <= 0 ){
			return "";
		}
		int max = -1;
		String res = "";
		int[][] result = new int[S.length() + 1][T.length() + 1];
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(S.charAt(i - 1) == T.charAt(j - 1)){
					result[i][j] = result[i- 1][j - 1] + 1;
				}else {
					result[i][j] = 0;
				}
				if(result[i][j] > max){
					max = result[i][j];
					res = S.substring(i - max , i);
				}
			}
		}
		return res;
	}
	
	
	
	public int delChar2(String string){
		if(string == null || string.length() <= 0){
			return 0;
		}
		String inverseString = new StringBuffer(string).reverse().toString();
		int common = longest(string, inverseString);
		return common;
	}
	
	
	//求最长公共子序列
	//压缩空间
	public int longest(String S, String T){
		if (S == null || T == null) {
			return -1;
		}
		if(S.length() <= 0  || T.length() <= 0 ){
			return 0;
		}
		int length = S.length();
		int tLength = T.length();
		int[] result = new int[tLength + 1];
		for (int i = 0; i < length; i++) {
			char c = S.charAt(i);
			int[] temp = Arrays.copyOf(result, tLength + 1);
			for (int j = 1; j <= tLength; j++) {
				if(c == T.charAt(j - 1)){
					result[j] = temp[j - 1] + 1;
				}else {
					result[j] = Math.max(result[j], result[j - 1]);
				}
			}
		}
		return result[tLength];
	}
	
	public int longest_2(String S, String T){
		if (S == null || T == null) {
			return -1;
		}
		if(S.length() <= 0  || T.length() <= 0 ){
			return 0;
		}
		int[][] result = new int[S.length() + 1][T.length() + 1];
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(S.charAt(i - 1) == T.charAt(j - 1)){
					result[i][j] = result[i- 1][j - 1] + 1;
				}else {
					result[i][j] = Math.max(result[i - 1][j], result[i][j - 1]);
				}
			}
		}
		return result[S.length()][T.length()];
	}
}

